package leetcode.code337;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

/**
 * 满树数组好用，不是满数组用不了
 *
 * @author CaoYu
 * @date 2021年8月10日
 * @description
 */
public class Solution5 {
	/**
	 * 数组并不是一棵满树
	 *
	 * @param args
	 */
	public static void main(String[] args) {
//		System.out.println(Math.pow(2, 2));
//		Integer[] array = new Integer[] { 3, 2, 3, null, 3, null, 1 };
		Integer[] array = new Integer[] { 4, 1, null, 2, null, 3 };
		TreeArray ta = new TreeArray();
		TreeNode root = TreeArray.array2tree(array);
		int result = rob(root);
		System.out.println(result);

//		System.out.println(root);
//		Integer[] array1 = ta.tree2array(root);
//		System.out.println(array1);
	}

	public static int rob(TreeNode root) {
		Integer[] array = tree2array(root);
		int len = array.length;
		int base = len + 1;
		int level = treeheight(root) - 1;
		int basestart = ((int) Math.pow(2, level - 1)) - 1;
		int result[][] = new int[len][2];
		for (int i = basestart; i < len; i++) {
			result[i][0] = 0;
			result[i][1] = array[i] == null ? 0 : array[i];
		}
		for (int i = basestart - 1; i > -1; i--) {
			int r = (2 * i + 1) * 2;
			int a = 0;// 孙
			int b = 0;
			int c = 0;
			int d = 0;
			if (r + 1 < len) {
				a = result[r + 1][1];
			}
			if (r + 2 < len) {
				b = result[r + 2][1];
			}
			if (r + 3 < len) {
				c = result[r + 3][1];
			}
			if (r + 4 < len) {
				d = result[r + 4][1];
			}
			result[i][1] = array[i] == null ? 0 : array[i] + a + b + c + d;
			int z1 = 0;
			int z2 = 0;
			if (2 * (i + 1) - 1 < len) {
				z1 = result[2 * (i + 1) - 1][1];
			}
			if (2 * (i + 1) < len) {
				z2 = result[2 * (i + 1)][1];
			}
			result[i][0] = z1 + z2;
		}
		return Math.max(result[0][0], result[0][1]);
	}

	/**
	 * 精简数组
	 *
	 * @param root
	 * @return
	 */
	public static Integer[] tree2array(TreeNode root) {
		if (root == null)
			return null;
		Queue<TreeNode> result = new LinkedList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			result.add(node);
			if (node == null) {
				continue;
			}
			if (node.left != null || node.right != null) {
				queue.add(node.left);
				queue.add(node.right);
			}
		}
		int len = result.size();
		Integer[] array = new Integer[len];
		for (int i = 0; i < len; i++) {
			TreeNode node = result.poll();
			if (node == null) {
				array[i] = null;
			} else {
				array[i] = node.val;
			}
		}
		return array;
	}

	public static int treeheight(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int left = treeheight(root.left);
		int right = treeheight(root.right);
		return left + right + 1;
	}
}
